package com.wm.algorithm.math;

/**
 * @ClassName: MediumMath
 * @Description: 中级数学运算
 * @Author: WM
 * @Date: 2023/8/13 20:52
 */
public class MediumMath {

    /**
     * 43. 字符串相乘
     * https://leetcode.cn/problems/multiply-strings/description/
     * 方法：数字位计算
     * 思路：两个数字相乘最终结果的位数不会超过两个数位数之和，所以先定义一个数组存储计算结果，使用两个索引i,j分别指向
     * 给定的两个数字的某位值上，指向的两个值相乘的结果正好对应res[i+j],res[i+j+1]两个位置。将计算的结果值和res[i+j+1]
     * 相加，值结果取余和取商即可计算出两个位置上的值。
     *
     * @param num1
     * @param num2
     * @return
     */
    // O(n^2)/O(m+n)
    public String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        // 结果最多为 m + n 位数
        int[] res = new int[m + n];
        // 结果最多为 m + n 位数
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                // 乘积在 res 对应的索引位置
                int p1 = i + j;
                int p2 = i + j + 1;
                // 叠加到 res 上
                int sum = res[p2] + mul;
                res[p2] = sum % 10;
                res[p1] += sum / 10;
            }
        }

        // 结果前缀可能存的 0（未使用的位）
        int i = 0;
        while (i < res.length && res[i] == 0) {
            i++;
        }

        // 将计算结果转化成字符串
        StringBuilder sbr = new StringBuilder();
        for (; i < res.length; i++) {
            sbr.append(res[i]);
        }
        return sbr.length() == 0 ? "0" : sbr.toString();
    }

}
